package com.jorenwu.asymmetric;

import java.math.BigInteger;
import java.util.Random;

public class MillerRabinPrimeTest implements PrimeTest
{
	BigInteger num;
	int round;

	public boolean primeTest(BigInteger num, int round)
	{
		this.num = num;
		this.round = round;
		return MRTest();
	}

	private boolean MRTest()
	{
		BigInteger m, k, a;
		k = BigInteger.ZERO;
		m = num.subtract(BigInteger.ONE);
		while (m.mod(BaseCalculator.TWO).equals(BigInteger.ZERO))
		{
			k = (BigInteger) k.add(BigInteger.ONE);
			m = (BigInteger) m.divide(BaseCalculator.TWO);
		}
		for (int count = 0; count < round; count++)
		{
			Random rand = new Random(System.currentTimeMillis());
			a = new BigInteger(num.bitCount(), rand);
			a = (BigInteger) (a.mod(num)).subtract(BigInteger.ONE);
			if (a.compareTo(BigInteger.ZERO) == 0)
				a.add(BaseCalculator.TWO);
			if (a.compareTo(BigInteger.ONE) == 0)
				a.add(BigInteger.ONE);
			a = (BigInteger) a.modPow(m, num);
			if (a.equals(BigInteger.ONE)
					|| a.equals(num.subtract(BigInteger.ONE)))
				return true;
			else
			{
				for (BigInteger counter = (BigInteger) BigInteger.ZERO; counter
						.compareTo(k) < 0; counter.add(BigInteger.ONE))
				{
					a = a.modPow(BaseCalculator.TWO, num);
					if (a.equals(BigInteger.ONE))
						return false;
					else if (a.equals(num.subtract(BigInteger.ONE)))
						return true;
					else return false;
				}
			}
		}
		return false;
	}

}
